package com.mzy.linear_struct.hot100.滑动窗口;

import java.util.HashMap;
import java.util.Objects;

/**
 * @Author: mizy3
 * @Date: 2024/07/04/上午10:58
 * @Description:
 */
public class Pro76最小覆盖子串 {


    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        HashMap<Character, Integer> win = new HashMap<>();

        for (char c : t.toCharArray()) {
            win.put(c, win.getOrDefault(c, 0) - 1);
        }
        int left = 0, right = 0;
        int cover = 0;
        int length = Integer.MAX_VALUE;
        int start = 0, end = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (win.containsKey(c)) {
                if (win.get(c) < 0) {
                    cover++;
                }
                win.put(c, win.get(c) + 1);
            }

            while (cover == t.length()) {
                // 记录符合条件的
                // 0123456789
                // ADOBECODEBANC
                // l
                //      r
                if (length > right - left + 1) {
                    start = left;
                    end = right;
                    length = right - left + 1;
                }


                char d = s.charAt(left);
                if (win.containsKey(d)) {
                    win.put(d, win.get(d) - 1);
                    if (win.get(d) < 0) {
                        cover--;
                    }
                }
                left++;
            }
            right++;
        }


        return length == Integer.MAX_VALUE ? "" : s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("EBBANCF", "ABC"));

    }
}













